package 链表和树.链表;
//Java：反转链表 II
public class ReverseLinkedListIi{
    public static void main(String[] args) {
        Solution solution = new ReverseLinkedListIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

  //Definition for singly-linked list.
//  public class ListNode {
//      int val;
//      ListNode next;
//      ListNode() {}
//      ListNode(int val) { this.val = val; }
//      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//  }
    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ///引入虚拟头节点是为了简化边界情况的处理，特别是当 left=1 时（需要反转的区间从头节点开始）。
            //有了虚拟节点，我们就不需要特殊处理头节点的情况。
            ListNode dummy = new ListNode(0, head);
            ListNode p0 = dummy;
            //这一步是找到反转区间的前一个节点在这个例子中是1
            for (int i = 0; i < left - 1; i++) {
                p0 = p0.next;
            }

            ListNode pre = null;
            ListNode cur = p0.next;
            for (int i = 0; i < right - left + 1; i++) {
                ListNode nxt = cur.next;
                cur.next = pre; // 每次循环只修改一个 next，方便大家理解
                pre = cur;
                cur = nxt;
            }
            //反转结束后pre指向反转这一段的末尾节点也就是4，cur指向反转这一段的下一个节点也就是5

            // 见视频
            p0.next.next = cur;
            p0.next = pre;
            return dummy.next;
        }


//leetcode submit region end(Prohibit modification and deletion)

    }
}